package J0120;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Solution1 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        //不用递归来实现前序遍历
        /*
            用栈来实现 根据先序遍历 根左右
            都往左边走 左边没有了再往右走
         */
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tmp = root;
        while(tmp != null || !stack.isEmpty()) {
            while(tmp != null) {
                stack.push(tmp);
                list.add(tmp.val);
                tmp = tmp.left;
            }
            //走到这里说明tmp.left为空 要走右边
            tmp = stack.pop().right;
        }
        return list;
    }
}
